package com.chj.leetcode.tijie250to300;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Code295_FindMedianFromDataStream2 {
	class MedianFinder {
		/** initialize your data structure here. */
		public MedianFinder() {
			maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
			minHeap = new PriorityQueue<Integer>(new MinHeapComparator());

		}

		private PriorityQueue<Integer> maxHeap;
		private PriorityQueue<Integer> minHeap;

		private void modifyTwoHeapsSize() {
			if (this.maxHeap.size() == this.minHeap.size() + 2) {
				this.minHeap.add(this.maxHeap.poll());
			}
			if (this.minHeap.size() == this.maxHeap.size() + 2) {
				this.maxHeap.add(this.minHeap.poll());
			}
		}

		public void addNum(int num) {
			if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
				maxHeap.add(num);

			} else {
				minHeap.add(num);
			}
			modifyTwoHeapsSize();
		}

		public double findMedian() {
			int maxHeapSize = this.maxHeap.size();
			int minHeapSize = this.minHeap.size();
			if (maxHeapSize + minHeapSize == 0) {
				return 0.0;
			}
			Integer maxHeapHead = this.maxHeap.peek();
			Integer minHeapHead = this.minHeap.peek();
			if (maxHeapSize == minHeapSize) {
				return (maxHeapHead + minHeapHead) * 0.5;
			}
			return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
		}

		public class MaxHeapComparator implements Comparator<Integer> {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (o2 > o1) {
					return 1;
				} else {
					return -1;
				}
			}
		}

		public class MinHeapComparator implements Comparator<Integer> {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (o2 < o1) {
					return 1;
				} else {
					return -1;
				}
			}
		}
	}
}
